package com.khiker.tree.binary_tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class P94_InorderTraversal {
	public List<Integer> inorderTraversal(TreeNode root) {
		List<Integer> list = new ArrayList<>(100);
		Stack<TreeNode> stack = new Stack<>();
		while (root != null || stack.size() > 0) {
			if (root == null) {
				root = stack.pop();
				list.add(root.val);
				root = root.right;
			} else {
				stack.push(root);
				root = root.left;
			}
		}
		return list;
	}
}
